package com.sourcetrip.algorithm.sort.radix;

import com.sourcetrip.utils.Integers;

/**
 * @author: xiaomi
 * @date: 2021/1/4
 * @description: 十大排序算法之九：基数排序（的对象比较版本，并不能比较自定义对象） --
 * 使用八进制（利用去位和取余的技巧进行优化）
 */
public class OctalRadixCustomedSortV0 extends RadixCustomedSortV0 {

    private int CONST_VALUE = 7;

    public OctalRadixCustomedSortV0() {
        super(8);
    }

    private OctalRadixCustomedSortV0(int k) {
        super(k);
    }


    //region    protected methods

    @Override
    protected int getMaxIndex(int max) {
        int res = 1;
        while ((max = (max >> 3)) > 0) {
            res++;
        }
        return res;
    }

    @Override
    protected int getRemainder(Integer item, int index) {
        int res = item;
        while (index-- > 0) {
            res = res >> 3;
        }
        return res & CONST_VALUE;
    }


    //endregion


    /**
     * 确实效率很高！
     * 1KW 只需要 3s
     * @param args
     */
    public static void main(String[] args) {
        Integer[] random = Integers.random(10_000_000, 10, 100_000_000);
        OctalRadixCustomedSortV0 sortV0 = new OctalRadixCustomedSortV0();
        sortV0.sort(random);
        System.out.println(sortV0);
        System.out.println(Integers.isAscOrder(random));
        //System.out.println(Arrays.toString(random));
    }
}
